package com.zp.self.module.level_4_算法练习.算法.动态规划;

import org.junit.Test;

/**
 * @author By ZengPeng
 */
public class 力扣_746_使用最小花费爬楼梯 {
    @Test
    public void main() {

        System.out.println(minCostClimbingStairs(new int[]{10,15,20}));
        System.out.println(minCostClimbingStairs(new int[]{1,100,1,1,1,100,1,1,100,1}));
    }

    /**
    题目：给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
     你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
     请你计算并返回达到楼梯顶部的最低花费。

     示例 1：
     输入：cost = [10,15,20]
     输出：15
     解释：你将从下标为 1 的台阶开始。
     - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
     总花费为 15 。

     示例 2：
     输入：cost = [1,100,1,1,1,100,1,1,100,1]
     输出：6
     解释：你将从下标为 0 的台阶开始。
     - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
     - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
     - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
     - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
     - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
     - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
     总花费为 6 。

    分析：【P 💔💔💔💔】 --你把这个题称为简单？？？！！！
       1.动态规划：dp[n] 表示：到达第i个点时，需要的最少费用
                    状态方程：f(0) = c[0]
                              f(1) = c[1]
                              f(2) = Min(f(0),f(1))+c[2]
                              f(3) = Min(f(1), f(2))+c[3]
                              .........
                              f(n-1) =Min(f(n-3), f(n-2))+c[3]
                    --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
             --时长：超过30分钟

    边界值 & 注意点：
       1.
     **/
    public int minCostClimbingStairs(int[] cost) {
        int proPro=cost[0],pro=cost[1],temp,length=cost.length;
        for (int i = 2; i < length; i++) {
           temp = Math.min(pro,proPro)+cost[i];
           proPro=pro;
           pro=temp;
        }
        return Math.min(proPro,pro);
    }
}
